package 代码随想录_动态规划.打家劫舍;

/**
 * @author zx
 * @create 2022-06-01 16:59
 * 组成部分一：确定状态
 *               最后一步：
 *               子问题：
 *               确定dp数组(dp table)以及下标的含义
 *               求一个节点偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。
 *               所以dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
 *               所以本题dp数组就是一个长度为2的数组！
 * 组成部分一：确定状态
 * 最后一步：
 * 子问题：
 * 组成部分二：转移方程
 * 偷当前节点,那么左右孩子就不能偷,val1 = root.val + left[0] + right[0];(对下标含义不理解就回顾一下dp数组的含义)
 * 不偷当前节点,左右孩子就可以偷,选一个最大的,所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);
 * 最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}
 * 组成部分三：初始条件和边界情况
 * 在遍历的过程中，如果遇到空间点的话，很明显，无论偷还是不偷都是0，所以就返回
 * if (root == null) {return new int[]{0, 0};}这也相当于dp数组的初始化
 * 其实这里的返回数组就是dp数组。
 * 组成部分四：计算顺序
 * 首先明确的是使用后序遍历。因为通过递归函数的返回值来做下一步计算。
 * 通过递归左节点，得到左节点偷与不偷的金钱。
 * 通过递归右节点，得到右节点偷与不偷的金钱。
 */
public class 打家劫舍III_337 {
    /**
     * @return 树形dp(入门)：难理解思维,但是看了代码又觉得不难
     */
    public int rob(TreeNode root) {
        int[] res = treeRob(root);
        return Math.max(res[0],res[1]);
    }
    //返回长度为2的数组,0：不偷,1：偷
    private int[] treeRob(TreeNode root){
        if (root == null) {
            return new int[]{0, 0};
        }
        int[] dpLeft = treeRob(root.left);
        int[] dpRight = treeRob(root.right);
        //偷当前节点,那么左右孩子就不能偷
        //下标为0记录不偷该节点所得到的的最大金钱,下标为1记录偷该节点所得到的的最大金钱
        int val1 = root.val + dpLeft[0] + dpRight[0];
        //不偷当前节点,那么左右孩子就可以偷,选一个最大的
        int val2 = Math.max(dpLeft[0], dpLeft[1]) + Math.max(dpRight[0], dpRight[1]);
        return new int[]{val2, val1};
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}